
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2130. -- [2010国家集训队]魔塔 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2130: [2010国家集训队]魔塔</h2><span class=green>Time Limit: </span>100 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>2&nbsp;&nbsp;<span class=green>Solved: </span>2<br>[<a href='submitpage.php?id=2130'>Submit</a>][<a href='problemstatus.php?id=2130'>Status</a>][<a href='bbs.php?id=2130'>Discuss</a>]</center><h2>Description</h2><div class=content>魔塔是一款很流行的益智类小游戏。在游戏中，你可以控制主人公在魔塔中移动，走到怪兽面前便可以和怪兽来决斗，打败怪兽后可以得到金钱，并可以通过金钱来提高自己的攻击力、防御力、血量，从而变得更强大。
然而，即便你拥有再高的攻击力、防御力，可以天下无敌，但一扇小小的门就可以阻止你无法前进。在游戏中，有红、黄、蓝三种颜色的门，并对应有红、黄、蓝三种颜色的钥匙。如果你想通过一扇门，需要消耗一把对应颜色的钥匙打开这扇门，如果你没有这种颜色的钥匙，便不能通过。
现在你得到一款加强版的魔塔游戏：
首先，门和钥匙的颜色不再是3种，而是n种，定为1~n号颜色。对于i号颜色的钥匙你有Ki把。并且之后你不会以任何形式得到任何颜色的钥匙。
在你面前有三座n层的魔塔A、B、C。每座魔塔的入口处和相邻两层之间都会有一扇门。对于每座魔塔，恰好有n扇门，并且这n扇门的颜色恰好各不相同。其中，A魔塔中通往第i层的门颜色为DoorAi。（DoorBi、DoorCi的定义与DoorAi类似）
在每座魔塔的每一层都有一定数量的怪兽，但这些怪兽根本打不过强大的你，你可以不费一滴血就秒杀这些怪兽，并得到杀死他们的金钱。我们已经为你统计好，消灭A魔塔第j层中所有的怪兽，可以得到的金钱数为GoldAi。（GoldBi、GoldCi的定义与GoldAi类似）
现在，就请你来决策，如何运用这些钥匙，能得到最多的金钱，并告诉我们最多能获得多少金钱。
</div><h2>Input</h2><div class=content>第一行一个字符（A~F），表示数据类型（在下面数据规模中有详细介绍）
第二行一个整数m，表示有几组测试数据。
之后给出m组数据，对于每组数据有九行：
    第一行一个整数n，表示魔塔层数。
第二行一个数列Ki。
第三行至第五行，每行一个数列，分别为DoorA、DoorB、DoorC。
第六行至第八行，每行一个数列，分别为GoldA、GoldB、GoldC。
第九行为一个空行。
</div><h2>Output</h2><div class=content>输出应包含m行，每行一个正整数，为最大能获得的金钱数。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>A<br />
2<br />
5<br />
1 2 1 1 2<br />
1 2 3 4 5<br />
2 4 3 5 1<br />
5 4 3 2 1<br />
1 1 1 1 5<br />
1 2 2 3 3<br />
1 2 1 1 1<br />
<br />
5<br />
1 2 1 1 2<br />
1 2 3 4 5<br />
2 4 3 5 1<br />
5 4 3 2 1<br />
1 1 1 1 50<br />
1 2 2 3 3<br />
1 2 1 1 1<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>12<br />
56<br />
【样例说明】<br />
对于第一个数据：<br />
1 2 3 4 5     第一个魔塔不用钥匙，能得到0金钱；<br />
2 4 3 5 1)    第二个魔塔用1、2、3、4、5号钥匙，得到11金钱；<br />
5)4 3 2 1     第三个魔塔用5号钥匙，得到1金钱；<br />
最多可得到12金钱。<br />
对于第二个数据：<br />
1 2 3 4 5)    第一个魔塔用1、2、3、4、5号钥匙，能得到54金钱；<br />
2)4 3 5 1     第二个魔塔用2号钥匙，得到1金钱；<br />
5)4 3 2 1     第三个魔塔用5号钥匙，得到1金钱；<br />
最多可得到56金钱。<br />
【数据规模】<br />
对于全部数据，满足：<br />
1<=m<=10；<br />
1<=n<=100000；<br />
1<=Ki<=2；<br />
0<= GoldAi、 GoldBi、 GoldCi <=2000；<br />
DoorA、DoorB、DoorC为三个1到n的排列。<br />
数据共分为六类：A、B、C、D、E、F，他们分别有各自的特征：<br />
A类数据占10%，保证n<=100。<br />
B类数据占10%，保证n<=1000。<br />
C类数据占10%，保证GoldCi=0，即第三座塔中没有任何金钱。<br />
D类数据占20%，保证Ki=1，即每种钥匙你都只有一把。<br />
E类数据占30%，保证DoorA、DoorB、DoorC三个1到n的排列为随机产生的数列。<br />
F类数据占20%，没有其他特征。<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=By 钱桥'>By 钱桥</a></p></div><center>[<a href='submitpage.php?id=2130'>Submit</a>][<a href='problemstatus.php?id=2130'>Status</a>][<a href='bbs.php?id=2130'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
